GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Rekursive Programmierung</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Rekursive Programmierung</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Bei der rekursiven Programmierung ruft sich eine <a href="Prozedur_(Programmierung)" title="Prozedur (Programmierung)">Prozedur</a>, <a href="Funktion_(Informatik)" class="mw-redirect" title="Funktion (Informatik)">Funktion</a> oder <a href="Unterprogramm#Terminologie" title="Unterprogramm">Methode</a> in einem <a href="Computerprogramm" title="Computerprogramm">Computerprogramm</a> selbst wieder auf (d. h. enthält eine <a href="Rekursion" title="Rekursion">Rekursion</a>). Auch der gegenseitige Aufruf stellt eine Rekursion dar.

Wichtig bei der <a href="Rekursion" title="Rekursion">rekursiven</a> <a href="Programmierung" title="Programmierung">Programmierung</a> ist eine <a href="Abbruchbedingung" title="Abbruchbedingung">Abbruchbedingung</a> in dieser <a href="Funktion_(Programmierung)" title="Funktion (Programmierung)">Funktion</a>, weil sich das rekursive <a href="Computerprogramm" title="Computerprogramm">Programm</a> sonst theoretisch unendlich oft selbst aufrufen würde.

Rekursive <a href="Programmierung" title="Programmierung">Programmierung</a> kann unter anderem in <a href="Prozedurale_Programmierung" title="Prozedurale Programmierung">prozeduralen</a> und <a href="Objektorientierte_Programmierung" title="Objektorientierte Programmierung">objektorientierten</a> <a href="Programmiersprache" title="Programmiersprache">Programmiersprachen</a> angewandt werden. Obwohl diese Sprachen in ihrem Sprachstandard die <a href="Rekursion" title="Rekursion">Rekursion</a> ausdrücklich zulassen, stellen Selbstaufrufe und gegenseitige Aufrufe hier (aufgrund der verwendeten <a href="Programmierparadigma" title="Programmierparadigma">Programmierparadigmen</a>) jedoch eher die Ausnahme dar. Auch wenn in der Praxis zur Verbesserung des <a href="Programmierstil" title="Programmierstil">Programmierstils</a> auch hier durchaus häufig auf Rekursion zurückgegriffen wird, sind die meisten <a href="Funktion_(Programmierung)" title="Funktion (Programmierung)">Funktionen</a> in diesen Sprachen doch rein <a href="Iterative_Programmierung" title="Iterative Programmierung">iterativ</a>.

In einigen Sprachen, wie z. B. in manchen <a href="Funktionale_Programmiersprache" class="mw-redirect" title="Funktionale Programmiersprache">funktionalen Programmiersprachen</a> oder <a href="Makroprozessor" title="Makroprozessor">Makroprozessoren</a>, muss die rekursive Programmiermethode zwingend verwendet werden, da <a href="Iterative_Programmierung" title="Iterative Programmierung">iterative</a> Sprachkonstrukte fehlen.

<div class="mw-heading mw-heading2"><h2 id="Beispiele">Beispiele</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Fakultät">Fakultät</h3></div>

Ein Beispiel für die Verwendung einer <a href="Rekursion" title="Rekursion">rekursiven</a> <a href="Programmierung" title="Programmierung">Programmierung</a> ist die Berechnung der <a href="Fakult%C3%A4t_(Mathematik)" title="Fakultät (Mathematik)">Fakultät</a> einer Zahl. Die Fakultät ist das <a href="Produkt_(Mathematik)" title="Produkt (Mathematik)">Produkt</a> aller ganzen Zahlen von 1 bis zu dieser Zahl. Die Fakultät von 4 ist also <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\cdot 2\cdot 3\cdot 4=24}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\cdot 2\cdot 3\cdot 4=24}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/55c21d2f5c8b7ad0888749f82f43fae50cac01ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:15.111ex; height:2.176ex;" alt="{\displaystyle 1\cdot 2\cdot 3\cdot 4=24}" loading="lazy">.

Mathematiker definieren die Fakultät meistens so (eine rekursive Definition):

<ul><li>Die Fakultät der Zahl 0 ist definitionsgemäß 1.</li>

<li>Die Fakultät einer ganzen Zahl, die größer als Null ist, ist das Produkt dieser Zahl mit der Fakultät der nächstkleineren ganzen Zahl.</li></ul>

Die Definition funktioniert so:

<dl><dd><ul><li>Will man die Fakultät von 4 berechnen, so muss man zunächst die Fakultät von 3 berechnen und das Ergebnis mit 4 multiplizieren.</li></ul>

<dl><dd><ul><li>Will man die Fakultät von 3 berechnen, so muss man zunächst die Fakultät von 2 berechnen und das Ergebnis mit 3 multiplizieren.</li></ul>

<dl><dd><ul><li>Will man die Fakultät von 2 berechnen, so muss man zunächst die Fakultät von 1 berechnen und das Ergebnis mit 2 multiplizieren.</li></ul>

<dl><dd><ul><li>Will man die Fakultät von 1 berechnen, so muss man zunächst die Fakultät von 0 berechnen und das Ergebnis mit 1 multiplizieren.</li></ul>

<dl><dd><ul><li>Die Fakultät von 0 ist nach Definition 1.</li></ul></dd></dl>

<ul><li>Die Fakultät von 1 ist also 1*1=1</li></ul></dd></dl>

<ul><li>Die Fakultät von 2 ist also 1*1*2=2</li></ul></dd></dl>

<ul><li>Die Fakultät von 3 ist also 1*1*2*3=6</li></ul></dd></dl>

<ul><li>Die Fakultät von 4 ist also 1*1*2*3*4=24</li></ul></dd></dl>

In einer <a href="Programmiersprache" title="Programmiersprache">Programmiersprache</a> wie Pascal, die rekursive Programmierung zulässt, kann man die <a href="Fakult%C3%A4t_(Mathematik)" title="Fakultät (Mathematik)">Fakultät</a> folgendermaßen eingeben:

Man definiert eine <a href="Funktion_(Programmierung)" title="Funktion (Programmierung)">Funktion</a> factorial, die eine Zahl x als Eingabewert bekommt. Diese Funktion multipliziert x mit dem Rückgabewert von factorial(x - 1) außer bei x = 0, dann liefert die Funktion das Ergebnis 1. Dies ist die Abbruchbedingung:

Rekursive Implementation der Fakultätsfunktion

<div class="mw-highlight mw-highlight-lang-pascal mw-content-ltr" dir="ltr"><pre>function factorial(x: Integer): Integer;

begin

if x = 0 then

factorial := 1

else

factorial := x * factorial(x - 1);

end;

</pre></div>

Mit der Startzahl x = 4 würde der <a href="Computer" title="Computer">Computer</a> rechnen:

<pre>4 * (3 * (2 * (1 * factorial(0))))

</pre>

heraus kommt dann das richtige Ergebnis, nämlich 24.

<div class="mw-heading mw-heading3"><h3 id="Binäre_Suche">Binäre Suche</h3></div>

Die <a href="Bin%C3%A4re_Suche" title="Binäre Suche">binäre Suche</a> in einem vorsortierten <a href="Feld_(Datentyp)" class="mw-redirect" title="Feld (Datentyp)">Array</a> lässt sich <a href="Rekursion" title="Rekursion">rekursiv</a> <a href="Implementierung" title="Implementierung">implementieren</a>. Wenn das mittlere Element kleiner als das gesuchte Element ist, wird die hintere Hälfte des Arrays rekursiv durchsucht. Wenn es größer als das gesuchte Element ist, wird die vordere Hälfte des Arrays rekursiv durchsucht. Ist es gleich dem gesuchten Element, ist die Suche beendet.

Die Abbruchbedingung für die <a href="Rekursion" title="Rekursion">Rekursion</a> ist erfüllt, wenn das mittlere Element gleich dem gesuchten Element ist, die Suche also erfolgreich ist, oder wenn der Endindex kleiner als der Startindex ist, die Suche also erfolglos ist.

Die folgende <a href="Funktion_(Programmierung)" title="Funktion (Programmierung)">Funktion</a> (<a href="Methode_(Programmierung)" title="Methode (Programmierung)">Methode</a>) für die <a href="Rekursion" title="Rekursion">rekursive</a> <a href="Bin%C3%A4re_Suche" title="Binäre Suche">binäre Suche</a> ist in der <a href="Programmiersprache" title="Programmiersprache">Programmiersprache</a> <a href="C-Sharp" title="C-Sharp">C#</a>:<div class="mw-highlight mw-highlight-lang-c# mw-content-ltr" dir="ltr"><pre>int RekursiveBinaereSuche(int[] werte, int gesuchterWert, int startIndex, int endIndex)

{

if (endIndex < startIndex)

{

// Wenn Element nicht gefunden, dann null zurückgeben

return null;

}

int mittlererIndex = (startIndex + endIndex) / 2;

if (werte[mittlererIndex] == gesuchterWert)

{

// Wenn Element gefunden, dann Index zurückgeben

return mittlererIndex;

}

else

{

if (werte[mittlererIndex] < gesuchterWert)

{

// Rekursiver Aufruf der Funktion für die hintere Hälfte

return RekursiveBinaereSuche(werte, gesuchterWert, mittlererIndex + 1, endIndex);

}

else

{

// Rekursiver Aufruf der Funktion für die vordere Hälfte

return RekursiveBinaereSuche(werte, gesuchterWert, startIndex, mittlererIndex - 1);

}

}

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Effizienz">Effizienz</h2></div>

<a href="Rekursion" title="Rekursion">Rekursive</a> <a href="Computerprogramm" title="Computerprogramm">Programme</a> haben in der Regel keine gute <a href="Performance_(Informatik)" class="mw-redirect" title="Performance (Informatik)">Performance</a>. Durch die wiederholten Funktionsaufrufe (Inkarnationen) wird immer wieder derselbe Methodeneintrittscode bearbeitet und bei jeder Inkarnation der <a href="Prozesskontext" title="Prozesskontext">Kontext</a> gesichert, was zu zusätzlichem <a href="Programmcode" title="Programmcode">Programmcode</a> und höherem <a href="Arbeitsspeicher" title="Arbeitsspeicher">Arbeitsspeicherverbrauch</a> führt. Alle rekursiven <a href="Algorithmus" title="Algorithmus">Algorithmen</a> lassen sich jedoch auch durch <a href="Iterative_Programmierung" title="Iterative Programmierung">iterative Programmierung</a> implementieren und umgekehrt.

<div class="mw-heading mw-heading3"><h3 id="Fakultät_2">Fakultät</h3></div>

Man hätte die <a href="Fakult%C3%A4t_(Mathematik)" title="Fakultät (Mathematik)">Fakultät</a> auch so <a href="Implementierung" title="Implementierung">implementieren</a> können:

var i, number: Integer;

begin

number := 1;

for i := 1 to x do

number := number * i;

factorial := number;

end;

</pre></div>

Hierbei gilt die Regel, dass für einfache Probleme eine <a href="Iterative_Programmierung" title="Iterative Programmierung">iterative</a> Implementierung häufig effizienter ist. So sollte z. B. auch die Fakultätsfunktion der Effizienz wegen in der Praxis iterativ implementiert werden. Bei komplizierten Problemstellungen (z. B. Aufgaben mit <a href="Baum_(Graphentheorie)" title="Baum (Graphentheorie)">Bäumen</a>) hingegen lohnt sich oftmals der Einsatz einer rekursiven Lösung, da für solche Probleme eine iterative Formulierung schnell sehr unübersichtlich – und ineffizient – werden kann, da im schlimmsten Fall der <a href="Stapelspeicher" title="Stapelspeicher">Stack</a> durch den iterativen <a href="Algorithmus" title="Algorithmus">Algorithmus</a> selbst verwaltet werden muss, was sonst der <a href="Prozessor" title="Prozessor">Prozessor</a> direkt erledigt.

Nicht alle <a href="H%C3%B6here_Programmiersprache" title="Höhere Programmiersprache">höheren Programmiersprachen</a> lassen rekursive Aufrufe zu. Ein Beispiel dazu ist älteres <a href="Fortran" title="Fortran">Fortran</a>. Ab Fortran 90 sind rekursive Aufrufe möglich. Andere <a href="Programmiersprache" title="Programmiersprache">Programmiersprachen</a> sind dagegen grundsätzlich rekursiv (wie z. B. <a href="Prolog_(Programmiersprache)" title="Prolog (Programmiersprache)">Prolog</a>). Solche rekursiven Programmiersprachen und auch andere Sprachen wie z. B. <a href="Scheme" title="Scheme">Scheme</a> setzen die <a href="Rekursion" title="Rekursion">Rekursion</a> meistens effizient um.

<div class="mw-heading mw-heading2"><h2 id="Implementierung">Implementierung</h2></div>

<a href="Rekursion" title="Rekursion">Rekursion</a> wird in der Regel durch einen <a href="Stapelspeicher" title="Stapelspeicher">Stack</a> implementiert, der die Rücksprungadressen, aber auch alle lokalen Variablen und eventuell Funktionsergebnisse aufnimmt. Würde man, wie im obenstehenden Beispiel, die <a href="Fakult%C3%A4t_(Mathematik)" title="Fakultät (Mathematik)">Fakultät</a> von 4 berechnen, so würde jeder Aufruf folgende Informationen auf den Stack legen:

<ol><li>Platz für Ergebnis</li>

<li>Argument x</li>

<li>Rücksprungadresse</li></ol>

Zunächst würde im Hauptprogramm also fac(4) aufgerufen und damit die folgenden Informationen auf den <a href="Stapelspeicher" title="Stapelspeicher">Stack</a> gelegt:

<td>Stapelanfang

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rightarrow }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/53e574cc3aa5b4bf5f3f5906caf121a378eef08b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.843ex;" alt="{\displaystyle \rightarrow }" loading="lazy">

</td>

<td bgcolor="#C0E0FF" align="center">1

</td>

<td bgcolor="#C0C0FF" align="center">Platz für Ergebnis

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0e0FF" align="center">2

</td>

<td bgcolor="#C0C0FF" align="center">4 (Argument)

</td></tr>

<tr>

<td>Stapelzeiger

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rightarrow }</annotation>

</semantics>

</td>

<td bgcolor="#C0E0FF" align="center">3

</td>

<td bgcolor="#C0C0FF" align="center">Rücksprungadresse ins Hauptprogramm

</td></tr></tbody></table>

Die Fakultätsfunktion prüft jetzt, ob das Argument 0 ist. Da dies nicht der Fall ist, wird 4*fac(3) berechnet. Zunächst muss also fac mit dem Argument 3 aufgerufen werden:

<td>Stapelanfang

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rightarrow }</annotation>

</semantics>

</td>

<td bgcolor="#C0E0FF" align="center">1

</td>

<td bgcolor="#C0C0FF" align="center">Platz für Ergebnis

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0e0FF" align="center">2

</td>

<td bgcolor="#C0C0FF" align="center">4 (Argument)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">3

</td>

<td bgcolor="#C0C0FF" align="center">Rücksprungadresse ins Hauptprogramm

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">4

</td>

<td bgcolor="#C0C0FF" align="center">Platz für Ergebnis

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0e0FF" align="center">5

</td>

<td bgcolor="#C0C0FF" align="center">3 (Argument)

</td></tr>

<tr>

<td>Stapelzeiger

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rightarrow }</annotation>

</semantics>

</td>

<td bgcolor="#C0E0FF" align="center">6

</td>

<td bgcolor="#C0C0FF" align="center">Rücksprungadresse in die Fakultätsfunktion

</td></tr></tbody></table>

Das Argument ist wieder ungleich 0, also geht’s weiter mit 3*fac(2).

<td>Stapelanfang

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rightarrow }</annotation>

</semantics>

</td>

<td bgcolor="#C0E0FF" align="center">1

</td>

<td bgcolor="#C0C0FF" align="center">Platz für Ergebnis

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0e0FF" align="center">2

</td>

<td bgcolor="#C0C0FF" align="center">4 (Argument)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">3

</td>

<td bgcolor="#C0C0FF" align="center">Rücksprungadresse ins Hauptprogramm

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">4

</td>

<td bgcolor="#C0C0FF" align="center">Platz für Ergebnis

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0e0FF" align="center">5

</td>

<td bgcolor="#C0C0FF" align="center">3 (Argument)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">6

</td>

<td bgcolor="#C0C0FF" align="center">Rücksprungadresse in die Fakultätsfunktion

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">7

</td>

<td bgcolor="#C0C0FF" align="center">Platz für Ergebnis

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0e0FF" align="center">8

</td>

<td bgcolor="#C0C0FF" align="center">2 (Argument)

</td></tr>

<tr>

<td>Stapelzeiger

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rightarrow }</annotation>

</semantics>

</td>

<td bgcolor="#C0E0FF" align="center">9

</td>

<td bgcolor="#C0C0FF" align="center">Rücksprungadresse in die Fakultätsfunktion

</td></tr></tbody></table>

Das Argument ist wieder ungleich 0, also2*fac(1).

<td>Stapelanfang

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rightarrow }</annotation>

</semantics>

</td>

<td bgcolor="#C0E0FF" align="center">1

</td>

<td bgcolor="#C0C0FF" align="center">Platz für Ergebnis

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0e0FF" align="center">2

</td>

<td bgcolor="#C0C0FF" align="center">4 (Argument)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">3

</td>

<td bgcolor="#C0C0FF" align="center">Rücksprungadresse ins Hauptprogramm

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">4

</td>

<td bgcolor="#C0C0FF" align="center">Platz für Ergebnis

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0e0FF" align="center">5

</td>

<td bgcolor="#C0C0FF" align="center">3 (Argument)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">6

</td>

<td bgcolor="#C0C0FF" align="center">Rücksprungadresse in die Fakultätsfunktion

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">7

</td>

<td bgcolor="#C0C0FF" align="center">Platz für Ergebnis

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0e0FF" align="center">8

</td>

<td bgcolor="#C0C0FF" align="center">2 (Argument)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">9

</td>

<td bgcolor="#C0C0FF" align="center">Rücksprungadresse in die Fakultätsfunktion

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">10

</td>

<td bgcolor="#C0C0FF" align="center">Platz für Ergebnis

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0e0FF" align="center">11

</td>

<td bgcolor="#C0C0FF" align="center">1 (Argument)

</td></tr>

<tr>

<td>Stapelzeiger

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rightarrow }</annotation>

</semantics>

</td>

<td bgcolor="#C0E0FF" align="center">12

</td>

<td bgcolor="#C0C0FF" align="center">Rücksprungadresse in die Fakultätsfunktion

</td></tr></tbody></table>

Das Argument ist wieder ungleich 0, also1*fac(0).

<td>Stapelanfang

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rightarrow }</annotation>

</semantics>

</td>

<td bgcolor="#C0E0FF" align="center">1

</td>

<td bgcolor="#C0C0FF" align="center">Platz für Ergebnis

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0e0FF" align="center">2

</td>

<td bgcolor="#C0C0FF" align="center">4 (Argument)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">3

</td>

<td bgcolor="#C0C0FF" align="center">Rücksprungadresse ins Hauptprogramm

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">4

</td>

<td bgcolor="#C0C0FF" align="center">Platz für Ergebnis

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0e0FF" align="center">5

</td>

<td bgcolor="#C0C0FF" align="center">3 (Argument)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">6

</td>

<td bgcolor="#C0C0FF" align="center">Rücksprungadresse in die Fakultätsfunktion

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">7

</td>

<td bgcolor="#C0C0FF" align="center">Platz für Ergebnis

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0e0FF" align="center">8

</td>

<td bgcolor="#C0C0FF" align="center">2 (Argument)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">9

</td>

<td bgcolor="#C0C0FF" align="center">Rücksprungadresse in die Fakultätsfunktion

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">10

</td>

<td bgcolor="#C0C0FF" align="center">Platz für Ergebnis

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0e0FF" align="center">11

</td>

<td bgcolor="#C0C0FF" align="center">1 (Argument)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">12

</td>

<td bgcolor="#C0C0FF" align="center">Rücksprungadresse in die Fakultätsfunktion

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">13

</td>

<td bgcolor="#C0C0FF" align="center">Platz für Ergebnis

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0e0FF" align="center">14

</td>

<td bgcolor="#C0C0FF" align="center">0 (Argument)

</td></tr>

<tr>

<td>Stapelzeiger

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rightarrow }</annotation>

</semantics>

</td>

<td bgcolor="#C0E0FF" align="center">15

</td>

<td bgcolor="#C0C0FF" align="center">Rücksprungadresse in die Fakultätsfunktion

</td></tr></tbody></table>

Jetzt ist das Argument 0, das Ergebnis also 1. Wir holen die Rücksprungadresse und das Argument vom <a href="Stapelspeicher" title="Stapelspeicher">Stack</a> und schreiben die 1 in den dafür vorgesehenen Platz. Der <a href="R%C3%BCcksprung" class="mw-redirect" title="Rücksprung">Rücksprung</a> führt in die Fakultätsfunktion zurück:

<td>Stapelanfang

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rightarrow }</annotation>

</semantics>

</td>

<td bgcolor="#C0E0FF" align="center">1

</td>

<td bgcolor="#C0C0FF" align="center">Platz für Ergebnis

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0e0FF" align="center">2

</td>

<td bgcolor="#C0C0FF" align="center">4 (Argument)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">3

</td>

<td bgcolor="#C0C0FF" align="center">Rücksprungadresse ins Hauptprogramm

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">4

</td>

<td bgcolor="#C0C0FF" align="center">Platz für Ergebnis

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0e0FF" align="center">5

</td>

<td bgcolor="#C0C0FF" align="center">3 (Argument)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">6

</td>

<td bgcolor="#C0C0FF" align="center">Rücksprungadresse in die Fakultätsfunktion

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">7

</td>

<td bgcolor="#C0C0FF" align="center">Platz für Ergebnis

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0e0FF" align="center">8

</td>

<td bgcolor="#C0C0FF" align="center">2 (Argument)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">9

</td>

<td bgcolor="#C0C0FF" align="center">Rücksprungadresse in die Fakultätsfunktion

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">10

</td>

<td bgcolor="#C0C0FF" align="center">Platz für Ergebnis

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0e0FF" align="center">11

</td>

<td bgcolor="#C0C0FF" align="center">1 (Argument)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">12

</td>

<td bgcolor="#C0C0FF" align="center">Rücksprungadresse in die Fakultätsfunktion

</td></tr>

<tr>

<td>Stapelzeiger

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rightarrow }</annotation>

</semantics>

</td>

<td bgcolor="#C0E0FF" align="center">13

</td>

<td bgcolor="#C0C0FF" align="center">1 (Ergebnis)

</td></tr></tbody></table>

Jetzt kann man das Ergebnis mit dem Argument multiplizieren (1*1). Das neue Ergebnis ist wieder 1. Die <a href="R%C3%BCcksprungadresse" class="mw-redirect" title="Rücksprungadresse">Rücksprungadresse</a> und das Argument werden vom <a href="Stapelspeicher" title="Stapelspeicher">Stack</a> geholt und das neue Ergebnis in den dafür vorgesehenen Platz geschrieben. <a href="R%C3%BCcksprung" class="mw-redirect" title="Rücksprung">Rücksprung</a> in die Fakultätsfunktion:

<td>Stapelanfang

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rightarrow }</annotation>

</semantics>

</td>

<td bgcolor="#C0E0FF" align="center">1

</td>

<td bgcolor="#C0C0FF" align="center">Platz für Ergebnis

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0e0FF" align="center">2

</td>

<td bgcolor="#C0C0FF" align="center">4 (Argument)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">3

</td>

<td bgcolor="#C0C0FF" align="center">Rücksprungadresse ins Hauptprogramm

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">4

</td>

<td bgcolor="#C0C0FF" align="center">Platz für Ergebnis

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0e0FF" align="center">5

</td>

<td bgcolor="#C0C0FF" align="center">3 (Argument)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">6

</td>

<td bgcolor="#C0C0FF" align="center">Rücksprungadresse in die Fakultätsfunktion

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">7

</td>

<td bgcolor="#C0C0FF" align="center">Platz für Ergebnis

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0e0FF" align="center">8

</td>

<td bgcolor="#C0C0FF" align="center">2 (Argument)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">9

</td>

<td bgcolor="#C0C0FF" align="center">Rücksprungadresse in die Fakultätsfunktion

</td></tr>

<tr>

<td>Stapelzeiger

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rightarrow }</annotation>

</semantics>

</td>

<td bgcolor="#C0E0FF" align="center">10

</td>

<td bgcolor="#C0C0FF" align="center">1 (Ergebnis)

</td></tr></tbody></table>

Wiederum wird das Ergebnis mit dem Argument multipliziert (1*2). Zurück in die Fakultätsfunktion:

<td>Stapelanfang

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rightarrow }</annotation>

</semantics>

</td>

<td bgcolor="#C0E0FF" align="center">1

</td>

<td bgcolor="#C0C0FF" align="center">Platz für Ergebnis

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0e0FF" align="center">2

</td>

<td bgcolor="#C0C0FF" align="center">4 (Argument)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">3

</td>

<td bgcolor="#C0C0FF" align="center">Rücksprungadresse ins Hauptprogramm

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">4

</td>

<td bgcolor="#C0C0FF" align="center">Platz für Ergebnis

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0e0FF" align="center">5

</td>

<td bgcolor="#C0C0FF" align="center">3 (Argument)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">6

</td>

<td bgcolor="#C0C0FF" align="center">Rücksprungadresse in die Fakultätsfunktion

</td></tr>

<tr>

<td>Stapelzeiger

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rightarrow }</annotation>

</semantics>

</td>

<td bgcolor="#C0E0FF" align="center">7

</td>

<td bgcolor="#C0C0FF" align="center">2 (Ergebnis)

</td></tr></tbody></table>

Das Ergebnis wird mit dem Argument multipliziert (2*3). Zurück in die Fakultätsfunktion:

<td>Stapelanfang

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rightarrow }</annotation>

</semantics>

</td>

<td bgcolor="#C0E0FF" align="center">1

</td>

<td bgcolor="#C0C0FF" align="center">Platz für Ergebnis

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0e0FF" align="center">2

</td>

<td bgcolor="#C0C0FF" align="center">4 (Argument)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td bgcolor="#C0E0FF" align="center">3

</td>

<td bgcolor="#C0C0FF" align="center">Rücksprungadresse ins Hauptprogramm

</td></tr>

<tr>

<td>Stapelzeiger

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rightarrow }</annotation>

</semantics>

</td>

<td bgcolor="#C0E0FF" align="center">4

</td>

<td bgcolor="#C0C0FF" align="center">6 (Ergebnis)

</td></tr></tbody></table>

Das Ergebnis wird mit dem Argument multipliziert (6*4). Zurück ins Hauptprogramm

<td>Stapelanfang Stapelzeiger

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rightarrow }</annotation>

</semantics>

</td>

<td bgcolor="#C0E0FF" align="center">1

</td>

<td bgcolor="#C0C0FF" align="center">24 (Ergebnis)

</td></tr></tbody></table>

Das Hauptprogramm muss dann nur noch das Ergebnis 24 vom <a href="Stapelspeicher" title="Stapelspeicher">Stack</a> holen.

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<ul><li><a href="Quicksort" title="Quicksort">Quicksort</a></li>

<li><a href="Endrekursion" title="Endrekursion">Endrekursion</a></li>

<li><a href="Programmierparadigma" title="Programmierparadigma">Programmierparadigma</a></li>

<li><a href="Entrekursivierung" title="Entrekursivierung">Entrekursivierung</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<div class="sisterproject" style="margin:0.1em 0 0 0;"><div class="noviewer" style="display:inline-block; line-height:10px; min-width:1.6em; text-align:center;" aria-hidden="true" role="presentation"></div><a href="https://de.wikibooks.org/wiki/Rekursive_Labyrinthe" class="extiw external" title="b:Rekursive Labyrinthe">Wikibooks: Rekursive Labyrinthe</a> – Lern- und Lehrmaterialien</div></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2024-12-03" href="https://de.wikipedia.org/wiki/?title=Rekursive_Programmierung&oldid=250920143">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>